There are a number of system applications where it is desireable to count the number of "ones" in a binary string in a fast, simple and efficient way. One such system is in the field of pattern recognition. In pattern recognition, histograms of a visual image or an audio signal are produced to provide a basis for statistical measurement thereof. In image pattern recognition, a histogram may be generated from the pixels along projection lines in the image. In audio pattern recognition, a histogram may be measured from the presence of the audio signal at predetermined energy levels. From the histograms, a comparison may be made between the present image or audio signal and a predetermined image or audio pattern to recognize a match.
In order to generate a histogram, the number of logic "one" pixels in the array of image pixels along the projection line or the number of logic "one" bits present in the array of an audio signal at a predetermined energy level must be determined. It may seem trivial like child's play to count the number of "ones". On the contrary, this computation is typically performed, for example, by executing at least 32 software instructions requiring at least 32 clock cycles for a 32 bit string. In addition, as the number of bits in the string increases, the processing time of the corresponding string increases in direct proportion. This laborious and time consuming software implementation has become unrealistic and impractical for system applications, such as pattern recognition, which demand real time processing.
Therefore, a need has arisen for an elegant, simple, and fast ones counting circuit and method which is directed to overcome the problems as set forth above.